Statement#

Given an array of positive integers arr and a target T, build an expression using these numbers by inserting a ++ or a - before each integer, and evaluating this expression. Find the total number of different expressions that evaluate to T.

For example, consider an array [1, 1] and a target 0, we can build the following expressions:

Expression

Sum

+ 1 + 1

2

+ 1 – 1

0

– 1 + 1

0

– 1 – 1

–2

The total number of expressions that evaluate to the target are 2.

Constraints:

  • 11 \leq arr.length 40\leq 40

  • 00 \leq arr[i] 1000\leq 1000

  • 00 \leq sum(arr[i]) 1000\leq 1000

  • 1000-1000 \leq T 1000\leq 1000

Examples#

No.

arr

T

Number of Expressions

1

[1, 2, 1]

0

2

2

[1, 1, 1, 1]

2

4

Try it yourself#

Implement your solution in the following playground.

Python
usercode > main.py
Input #1
Input #2
Target Sum

Note: If you clicked the "Submit" button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution#

We will first explore the naive recursive solution to this problem and then see how it can be improved using the 0/1 Knapsack dynamic programming pattern.

Naive approach#

A naive approach to this problem is to find all expressions using the given numbers and then count the number of expressions that evaluate to the given target.

For example, we have an array [2, 1, 2], and we can build the following expressions:

  • +2+1+2=5+2+1+2=5
  • +21+2=3+2-1+2=3
  • 2+1+2=1-2+1+2=1
  • 21+2=1-2-1+2=-1
  • +2+12=1+2+1-2=1
  • +212=1+2-1-2=-1
  • 2+12=3-2+1-2=-3
  • 212=5-2-1-2=-5

Now, for a given target, we can count the number of expressions that evaluate to that target. For example, if the target is –1, we can count that 2 expressions evaluate to –1.

The calculation above shows that we need a recursive solution to make all possible expressions. In other words, we divide the problem into subproblems, and for each number, we place a ++ or - before it and generate new expressions.

Let’s implement the algorithm as discussed above:

Target Sum using recursion

Note: Please observe that if you include the test case commented out in the driver code, the solution is likely to time out. Try to solve the larger problem using the dynamic programming solutions provided below and see the difference.

Time complexity#

The time complexity of the naive approach is O(2n)O(2^n), where nn is the total number of integers. This is because we have two possible choices every time, either to assign a ++ or a - sign to the array elements.

Space complexity#

As the maximum depth of the recursive call tree is nn, and each call stores its data on the stack, the space complexity of this approach is O(n)O(n).

Optimized solution using dynamic programming#

Now, let us improve the recursive solution using top-down and bottom-up approaches.

Top-down solution#

The top-down solution, commonly known as the memoization technique, is an enhancement of the recursive solution. It overcomes the problem of calculating redundant solutions over and over again by storing them in an array.

In the recursive solution, when we generate two new expressions by inserting a ++ or a - before a number, all the array elements before the current element are computed. However, we had already evaluated them in the previous recursive calls. For example, consider an array [1, 2, 1]. Suppose we have already processed the first two elements. For the last element, two new expressions can be generated by placing a ++ or a - before it. While evaluating these expressions, the first two elements will be processed again, although we have already computed them in previous iterations. This becomes obvious when we list down all the possible expressions:

  • +1+2+1=4\color{Green}+1+2\color{Black}+1=4
  • +12+1=0\color{Orange}+1-2\color{Black}+1=0
  • 1+2+1=2\color{Blue}-1+2\color{Black}+1=2
  • 12+1=2\color{Red}-1-2\color{Black}+1=-2
  • +1+21=2\color{Green}+1+2\color{Black}-1=2
  • +121=2\color{Orange}+1-2\color{Black}-1=-2
  • 1+21=0\color{Blue}-1+2\color{Black}-1=0
  • 121=4\color{Red}-1-2\color{Black}-1=-4

This results in many redundant recursive calls. To avoid this, we create a lookup table called dp of nn rows and 2sum(arr)+12*sum(arr)+1 columns. The number of rows represents the number of given integers and the number of columns represents all possible target sums that can be built using these integers. For any given integer, whenever we generate and evaluate an expression, we store it at dp[i][T], where i and T represent the index of the integer and the generated sum, respectively. At any later time, if we encounter the same expression, we can return the stored result from the table with an O(1)O(1) lookup time instead of recalculating that expression.

Let’s implement the algorithm as discussed above:

Target Sum using memoization

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

As we avoided redundant calculations by storing all the intermediate results in a lookup table, the time complexity of this approach is reduced to O(n×k)O(n \times k), where nn is the size of the array and k=sum(arr)k=sum(arr).

Space complexity#

The space taken by the lookup table is O(n×k)O(n \times k), where nn is the size of the array and k=sum(arr)k=sum(arr).

Bottom-up solution#

The bottom-up solution, also known as the tabulation technique, is an iterative method of solving dynamic programming problems. Here, we will again create a lookup table of size n×2sum(arr)+1n \times 2*sum(arr)+1. The table is initialized with 0 except for the indexes corresponding to the first integer. Two expressions can be generated using the first integer by inserting a ++ or a - before it. Therefore, we store 1 at the respective indices.

As we see in the code below, the algorithm iterates over all integers and for every possible target sum t, it checks if it was generated during the previous iterations i.e., if dp[i-1][total+t] > 0, where total is the sum of all elements of the array. If it was generated, two new expressions are considered by inserting a ++ or a - before the current integer and the count of expressions is increased i.e., dp[i-1][total+t] is added to the values of dp[i][total+t+arr[i]] and dp[i][total+t-arr[i]].

Let’s look at the following illustration to get a better understanding of the solution:

Created with Fabric.js 3.6.6 -4 -3 -2 -1 0 1 2 3 4 0 1 2 3 4 5 6 7 8 1 0 0 0 0 1 0 1 0 0 0 2 1 0 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 0 0 0

1 of 20

Created with Fabric.js 3.6.6 -4 -3 -2 -1 0 1 2 3 4 0 1 2 3 4 5 6 7 8 1 0 0 0 0 1 0 1 0 0 0 2 1 0 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 0 0 0

2 of 20

Created with Fabric.js 3.6.6 -4 -3 -2 -1 0 1 2 3 4 0 1 2 3 4 5 6 7 8 1 0 0 0 0 1 0 1 0 0 0 2 1 0 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 0 0 0

3 of 20

Created with Fabric.js 3.6.6 -4 -3 -2 -1 0 1 2 3 4 0 1 2 3 4 5 6 7 8 1 0 0 0 0 1 0 1 0 0 0 2 1 0 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 0 0 0

4 of 20

Created with Fabric.js 3.6.6 -4 -3 -2 -1 0 1 2 3 4 0 1 2 3 4 5 6 7 8 1 0 0 0 0 1 0 1 0 0 0 2 1 0 1 0 0 0 1 0 0 0 1 2 0 0 0 0 0 0 0 0 0

5 of 20

Created with Fabric.js 3.6.6 -4 -3 -2 -1 0 1 2 3 4 0 1 2 3 4 5 6 7 8 1 0 0 0 0 1 0 1 0 0 0 2 1 0 1 0 0 0 1 0 0 0 1 2 0 0 0 0 0 0 0 0 0

6 of 20

Created with Fabric.js 3.6.6 -4 -3 -2 -1 0 1 2 3 4 0 1 2 3 4 5 6 7 8 1 0 0 0 0 1 0 1 0 0 0 2 1 0 1 0 1 0 1 0 1 0 1 2 0 0 0 0 0 0 0 0 0

7 of 20

Created with Fabric.js 3.6.6 -4 -3 -2 -1 0 1 2 3 4 0 1 2 3 4 5 6 7 8 1 0 0 0 0 1 0 1 0 0 0 2 1 0 1 0 1 0 1 0 1 0 1 2 0 0 0 0 0 0 0 0 0

8 of 20

Created with Fabric.js 3.6.6 -4 -3 -2 -1 0 1 2 3 4 0 1 2 3 4 5 6 7 8 1 0 0 0 0 1 0 1 0 0 0 2 1 0 1 0 1 0 1 0 1 0 1 2 0 0 0 0 0 0 0 0 0

9 of 20

Created with Fabric.js 3.6.6 -4 -3 -2 -1 0 1 2 3 4 0 1 2 3 4 5 6 7 8 1 0 0 0 0 1 0 1 0 0 0 2 1 0 1 0 1 0 1 0 1 0 1 2 0 0 0 0 0 0 0 0 0

10 of 20

Created with Fabric.js 3.6.6 -4 -3 -2 -1 0 1 2 3 4 0 1 2 3 4 5 6 7 8 1 0 0 0 0 1 0 1 0 0 0 2 1 0 1 0 1 0 1 0 1 0 1 2 0 0 0 0 0 0 0 0 0

11 of 20

Created with Fabric.js 3.6.6 -4 -3 -2 -1 0 1 2 3 4 0 1 2 3 4 5 6 7 8 1 0 0 0 0 1 0 1 0 0 0 2 1 0 1 0 1 0 1 0 1 0 1 2 1 0 1 0 0 0 0 0 0

12 of 20

Created with Fabric.js 3.6.6 -4 -3 -2 -1 0 1 2 3 4 0 1 2 3 4 5 6 7 8 1 0 0 0 0 1 0 1 0 0 0 2 1 0 1 0 1 0 1 0 1 0 1 2 1 0 1 0 0 0 0 0 0

13 of 20

Created with Fabric.js 3.6.6 -4 -3 -2 -1 0 1 2 3 4 0 1 2 3 4 5 6 7 8 1 0 0 0 0 1 0 1 0 0 0 2 1 0 1 0 1 0 1 0 1 0 1 2 1 0 2 0 1 0 0 0 0

14 of 20

Created with Fabric.js 3.6.6 -4 -3 -2 -1 0 1 2 3 4 0 1 2 3 4 5 6 7 8 1 0 0 0 0 1 0 1 0 0 0 2 1 0 1 0 1 0 1 0 1 0 1 2 1 0 2 0 1 0 0 0 0

15 of 20

Created with Fabric.js 3.6.6 -4 -3 -2 -1 0 1 2 3 4 0 1 2 3 4 5 6 7 8 1 0 0 0 0 1 0 1 0 0 0 2 1 0 1 0 1 0 1 0 1 0 1 2 1 0 2 0 2 0 1 0 0

16 of 20

Created with Fabric.js 3.6.6 -4 -3 -2 -1 0 1 2 3 4 0 1 2 3 4 5 6 7 8 1 0 0 0 0 1 0 1 0 0 0 2 1 0 1 0 1 0 1 0 1 0 1 2 1 0 2 0 2 0 1 0 0

17 of 20

Created with Fabric.js 3.6.6 -4 -3 -2 -1 0 1 2 3 4 0 1 2 3 4 5 6 7 8 1 0 0 0 0 1 0 1 0 0 0 2 1 0 1 0 1 0 1 0 1 0 1 2 1 0 2 0 2 0 2 0 1

18 of 20

Created with Fabric.js 3.6.6 -4 -3 -2 -1 0 1 2 3 4 0 1 2 3 4 5 6 7 8 1 0 0 0 0 1 0 1 0 0 0 2 1 0 1 0 1 0 1 0 1 0 1 2 1 0 2 0 2 0 2 0 1

19 of 20

Created with Fabric.js 3.6.6 -4 -3 -2 -1 0 1 2 3 4 0 1 2 3 4 5 6 7 8 1 0 0 0 0 1 0 1 0 0 0 2 1 0 1 0 1 0 1 0 1 0 1 2 1 0 2 0 2 0 2 0 1

20 of 20

Let's implement the algorithm as discussed above:

Target Sum using tabulation

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

The time complexity of this algorithm is O(n×k)O(n \times k), where nn is the size of the array and k=sum(arr)k=sum(arr).

Space complexity#

The space complexity of this algorithm is O(n×k)O(n \times k).

Can we do better?

We can further improve the bottom-up approach by using a two dimensional lookup table of size 2×2sum(arr)+12 \times 2*sum(arr)+1 instead of n×2sum(arr)+1n \times 2*sum(arr)+1. We can observe in the above algorithm that while filling up the cells of a specific row, we always require the values of the previous row; that is, for filling the cells dp[i][j+arr[i]] and dp[i][j-arr[i]], we require the value of dp[i-1][j]. Therefore, there is no point in storing all the previous rows. Instead, we can start by filling the first row of the lookup table ourselves. For each subsequent row, we compute all the values using the first row and store them in the second row of the lookup table. Then, we replace the first row with the second one so it can be used in the next iteration.

The time complexity will remain the same, O(n×k)O(n \times k), because we still have to do the calculations for all integers and all possible target sums. The space complexity, however, reduces to O(k)O(k) since we are only using a lookup table of two rows.

Solving the 0/1 Knapsack Problem

Subset Sum